package com.zs.letcode.tencent;

/**
 * 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * <p>
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * <p>
 * 输入：s = "ac"
 * 输出："a"
 *
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母（大写和/或小写）组成
 * 相关标签
 * 字符串
 * 动态规划
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/tencent/xxk4s2/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/7/6 13:02
 */
public class Chapter3 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：动态规划
         */
        public String longestPalindrome(String s) {
            int len = s.length();
            if (len < 2) {
                return s;
            }
            int maxLen = 1, begin = 0;
            // dp[i][j] 表示 s[i..j] 是否是回文串
            boolean[][] dp = new boolean[len][len];
            // 初始化：所有长度为 1 的子串都是回文串
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }
            char[] charArray = s.toCharArray();
            // 递推开始
            // 先枚举子串长度
            for (int L = 2; L <= len; L++) {
                // 枚举左边界，左边界的上限设置可以宽松一些
                for (int i = 0; i < len; i++) {
                    // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                    int j = L + i - 1;
                    // 如果右边界越界，就可以退出当前循环
                    if (j >= len) {
                        break;
                    }
                    if (charArray[i] != charArray[j]) {
                        dp[i][j] = false;
                    } else {
                        if (j - i < 3) {
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }
                    // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                    if (dp[i][j] && j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }

        /**
         * 动态规划
         */
        public static String longestPalindrome1(String s) {
            //边界条件判断
            if (s.length() < 2)
                return s;
            //start表示最长回文串开始的位置，
            //maxLen表示最长回文串的长度
            int start = 0, maxLen = 1;
            int length = s.length();
            boolean[][] dp = new boolean[length][length];
            for (int right = 0; right < length; right++) {
                for (int left = 0; left < right; left++) {
                    //如果两种字符不相同，肯定不能构成回文子串
                    if (s.charAt(left) != s.charAt(right)) {
                        continue;
                    }
                    //下面是s.charAt(left)和s.charAt(right)两个
                    //字符相同情况下的判断
                    //如果只有一个字符，肯定是回文子串
                    if (right == left) {
                        dp[left][right] = true;
                    } else if (right - left <= 2) {
                        //类似于"aa"和"aba"，也是回文子串
                        dp[left][right] = true;
                    } else {
                        //类似于"a******a"，要判断他是否是回文子串，只需要
                        //判断"******"是否是回文子串即可
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                    //如果字符串从left到right是回文子串，只需要保存最长的即可
                    if (dp[left][right] && right - left + 1 > maxLen) {
                        maxLen = right - left + 1;
                        start = left;
                    }
                }
            }
            //截取最长的回文子串
            return s.substring(start, start + maxLen);
        }

        /**
         * 中心扩散法
         */
        public String longestPalindrome2(String s) {
            // 边界条件判断
            if (s.length() < 2)
                return s;
            // start表示最长回文串开始的位置，
            // maxLen表示最长回文串的长度
            int start = 0, maxLen = 0;
            int length = s.length();
            for (int i = 0; i < length; ) {
                // 如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环
                // （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断）
                if (length - i <= maxLen / 2)
                    break;
                int left = i, right = i;
                while (right < length - 1 && s.charAt(right + 1) == s.charAt(right)) {
                    //过滤掉重复的
                    right++;
                }
                //下次在判断的时候从重复的下一个字符开始判断
                i = right + 1;
                //然后往两边判断，找出回文子串的长度
                while (right < length - 1 && left > 0 && s.charAt(right + 1) == s.charAt(left - 1)) {
                    right++;
                    left--;
                }
                //保留最长的
                if (right - left + 1 > maxLen) {
                    start = left;
                    maxLen = right - left + 1;
                }
            }
            //截取回文子串
            return s.substring(start, start + maxLen);
        }
    }
}
